package com.myc.subjects.sort;

import java.util.Arrays;
import java.util.List;
import java.util.Random;

/**
 * LeetCode题号：215
 *
 * 数组中的第k个最大元素
 *
 * 给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。
 * 请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。
 *
 * 示例 1:
 * 输入: [3,2,1,5,6,4] 和 k = 2
 * 输出: 5
 *
 * 示例2:
 * 输入: [3,2,3,1,2,4,5,5,6] 和 k = 4
 * 输出: 4
 *
 * 提示：
 * 1 <= k <= nums.length <= 104
 * -104 <= nums[i] <= 104
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/kth-largest-element-in-an-array
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */

public class Shuzuzhongdedikgezuidayuansu {

    public static void main(String[] args) {
        Shuzuzhongdedikgezuidayuansu s = new Shuzuzhongdedikgezuidayuansu();
        //int[] nums = new int[]{3,2,3,1,2,4,5,5,6};
        //int k = 4;
        int[] nums = new int[]{2, 1};
        int k = 2;
        System.out.println(s.findKthLargest2(nums, k));
    }

    /**
     * 方法一：快速选择（基于快速排序的选择）
     * 时间复杂度：O(n) 证明比较复杂，参考算法导论第9章
     * 在快速排序中我们采用分治思想，进行排序，这一题，我们利用这种思想，进行查找第k大的元素。
     * 以数组中一个随机下标的元素为基准元素，利用分区方法找到该基准元素的基准位置。
     * 如果基准位置比nums.length - k小，递归调用基准位置右边的子数组，反之，递归调用基准位置左边的子数组。
     * 直到基准位置与nums.length - k重合，此时基准元素就是第k个最大元素
     */
    public int findKthLargest1(int[] nums, int k) {
        //由于题目给的方法参数不足以用于递归调用需要，所以我们另使用一个方法来实现递归方法
        return quickSelect(nums, 0, nums.length - 1, k);
    }

    //快速选择递归方法
    public int quickSelect(int[] nums, int start, int end, int k){
        //先找到基准位置
        int position = partition(nums, start, end);

        //如果基准位置与nums.length - k重合，此时基准元素就是第k个最大元素
        if(position == nums.length - k) return nums[position];//边界情况

        //否则根据条件分别递归调用左子数组或右子数组
        if(position > nums.length - k) return quickSelect(nums, start, position - 1, k);
        else return quickSelect(nums, position + 1, end, k);
    }

    //分区方法
    public int partition(int[] nums, int start, int end){
        //随机选取一个元素作为基准元素
        Random rand = new Random();
        int randomIndex = start + rand.nextInt(end - start + 1);
        int pivot = nums[randomIndex];

        //将基准元素与第一个元素交换，方便后面执行分区操作
        swap(nums, start, randomIndex);

        //利用左右指针开始分区
        int left = start, right = end;
        while (left < right){
            while(left < right && nums[right] >= pivot) right--;
            nums[left] = nums[right];
            while(left < right && nums[left] <= pivot) left++;
            nums[right] = nums[left];
        }
        nums[left] = pivot;
        return left;
    }

    /**
     * 方法二：基于堆排序的选择
     * 时间复杂度：O(n*log^n)
     * 使用数组模拟一个大顶堆的结构，再移除 k - 1 次堆顶元素之后，此时的堆顶元素就是第 k 大的元素
     */
    public int findKthLargest2(int[] nums, int k) {

        //首先构建大顶堆
        buildMaxHeap(nums, nums.length);
        int heapSize = nums.length;//定义大顶堆的大小

        //做 k - 1 次去掉堆顶元素的操作
        for(int i = nums.length - 1; i > nums.length - k; i--){
            //首先将堆顶元素与最后一个元素交换
            swap(nums, 0, heapSize - 1);
            //逻辑删除最后一个元素
            heapSize--;
            //再对新的堆顶元素做一次下沉
            maxHeapify(nums, 0, heapSize);
        }

        //此时堆顶元素就是第k个最大元素
        return nums[0];
    }

    //构建大顶堆方法
    public void buildMaxHeap(int[] nums, int heapSize){
        //将数组想象成一个完全二叉树，数组下标就是完全二叉树节点的编号，堆顶元素编号为0
        //然后从最后一个非叶子节点开始，对每一个非叶子节点，做一次下沉操作，一直到堆顶元素。
        //对于编号从0开始的完全二叉树而言，叶子节点永远与非叶子节点的数量相等或大1，所以最后一个非叶子节点的编号就是 heapSize / 2 - 1
        for(int i = heapSize / 2 - 1; i >= 0; i--){
            maxHeapify(nums, i, heapSize);
        }
    }

    //大顶堆中元素下沉的方法
    public void maxHeapify(int[] nums, int top, int heapSize){

        //通过顶部节点位置，找到它的左右两个节点的位置
        int largest = top;
        int left = 2 * largest + 1;
        int right = 2 * largest + 2;

        //比较顶部节点与其左右两个子节点位置的大小，找到最大的那个值
        if(right < heapSize && nums[right] > nums[largest]) largest = right;
        if(left < heapSize && nums[left] > nums[largest]) largest = left;

        //如果最大的值不是顶部节点，则交换最大节点和顶部节点，同时递归调用最大的那个节点交换前的位置
        if(largest != top){
            swap(nums, top, largest);
            maxHeapify(nums, largest, heapSize);
        }
    }

    //交换数组中两个元素的方法
    public void swap(int[] nums, int index1, int index2){
        int temp = nums[index1];
        nums[index1] = nums[index2];
        nums[index2] = temp;
    }

}


//官方题解
//方法一：基于快速排序的选择方法
//class Solution {
//    Random random = new Random();
//
//    public int findKthLargest(int[] nums, int k) {
//        return quickSelect(nums, 0, nums.length - 1, nums.length - k);
//    }
//
//    public int quickSelect(int[] a, int l, int r, int index) {
//        int q = randomPartition(a, l, r);
//        if (q == index) {
//            return a[q];
//        } else {
//            return q < index ? quickSelect(a, q + 1, r, index) : quickSelect(a, l, q - 1, index);
//        }
//    }
//
//    public int randomPartition(int[] a, int l, int r) {
//        int i = random.nextInt(r - l + 1) + l;
//        swap(a, i, r);
//        return partition(a, l, r);
//    }
//
//    public int partition(int[] a, int l, int r) {
//        int x = a[r], i = l - 1;
//        for (int j = l; j < r; ++j) {
//            if (a[j] <= x) {
//                swap(a, ++i, j);
//            }
//        }
//        swap(a, i + 1, r);
//        return i + 1;
//    }
//
//    public void swap(int[] a, int i, int j) {
//        int temp = a[i];
//        a[i] = a[j];
//        a[j] = temp;
//    }
//}

//方法二：基于堆排序的选择方法
//class Solution {
//    public int findKthLargest(int[] nums, int k) {
//        int heapSize = nums.length;
//        buildMaxHeap(nums, heapSize);
//        for (int i = nums.length - 1; i >= nums.length - k + 1; --i) {
//            swap(nums, 0, i);
//            --heapSize;
//            maxHeapify(nums, 0, heapSize);
//        }
//        return nums[0];
//    }
//
//    public void buildMaxHeap(int[] a, int heapSize) {
//        for (int i = heapSize / 2; i >= 0; --i) {
//            maxHeapify(a, i, heapSize);
//        }
//    }
//
//    public void maxHeapify(int[] a, int i, int heapSize) {
//        int l = i * 2 + 1, r = i * 2 + 2, largest = i;
//        if (l < heapSize && a[l] > a[largest]) {
//            largest = l;
//        }
//        if (r < heapSize && a[r] > a[largest]) {
//            largest = r;
//        }
//        if (largest != i) {
//            swap(a, i, largest);
//            maxHeapify(a, largest, heapSize);
//        }
//    }
//
//    public void swap(int[] a, int i, int j) {
//        int temp = a[i];
//        a[i] = a[j];
//        a[j] = temp;
//    }
//}

/**
 * 总结：
 * 1.需要找我快速选择的基本实现方式，以及其指导思想：分治策略。这个算法类似二分查找，但因为数组无序，没有办法找到中间的那个数，所以，随机选取一个数，直接进行二分。
 * 2.基于堆排序的选择是利用数组去模拟一个大顶堆的方式去排序，其思想很好理解。要掌握数组模拟完全二叉树的一些特点，以及其他的技巧。
 */
